package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor
 * <p>
 * 给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
 * <p>
 * （如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
 *
 * @author hanjuntao
 * @date 2025/9/3 0003
 */
public class L_1026_节点与其祖先的最大差值 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.left.right.left = new TreeNode(4);
        root.left.right.right = new TreeNode(7);
        root.right.right = new TreeNode(14);
        root.right.right.left = new TreeNode(13);

        System.out.println(maxAncestorDiff3(root)); // 7
    }

    /**
     * 思路：
     * <p>
     * 最大差值计算逻辑：
     * 1. 计算当前节点和当前路径中节点的最小值和最大值之间的差值
     * a = |curr.val - min|
     * b = |curr.val - max|
     * <p>
     * 2. 取出两个值中的最大值
     * maxDiff = max(a, b)
     * <p>
     * 基于以上理论，采用从顶到下的递归方式进行计算
     * 在dfs遍历过程中，需要维护当前路径的最大值和最小值，并向下传递，并记录最大差值
     *
     * @param root
     * @return
     */
    public static int maxAncestorDiff2(TreeNode root) {
        AtomicInteger ai = new AtomicInteger(Integer.MIN_VALUE);

        dfs(root, root.val, root.val, ai);
        return ai.get();
    }

    private static void dfs(TreeNode root, int min, int max, AtomicInteger ai) {
        if (root == null) {
            return;
        }

        // 计算最值
        min = Math.min(min, root.val);
        max = Math.max(max, root.val);

        // 计算差值
        int diff1 = Math.abs(root.val - min);
        int diff2 = Math.abs(root.val - max);

        ai.set(Math.max(ai.get(), Math.max(diff1, diff2)));

        dfs(root.left, min, max, ai);
        dfs(root.right, min, max, ai);
    }

    /**
     * 采用自底向上的思路
     * <p>
     * 对于任意节点，计算出左右子树的最小值和最大值，
     * 然后再计算分别计算节点的差值，并更新结果。
     * <p>
     * 这个思路是自底向上的，从叶子节点开始，向上计算。这就要求递归函数返回子树的最小值和最大值。
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     *
     * @param root
     * @return
     */
    public static int maxAncestorDiff3(TreeNode root) {
        AtomicInteger ai = new AtomicInteger(Integer.MIN_VALUE);

        dfs3(root, ai);

        return ai.get();
    }

    private static int[] dfs3(TreeNode root, AtomicInteger ai) {
        if (root == null) {
            return null;
        }

        int[] left = dfs3(root.left, ai);
        int[] right = dfs3(root.right, ai);

        int min = root.val;
        int max = root.val;

        if (left != null) {
            // 计算最值
            min = Math.min(left[0], min);
            max = Math.max(left[1], max);

            // 计算差值
            int diff1 = Math.abs(root.val - min);
            int diff2 = Math.abs(root.val - max);

            ai.set(Math.max(ai.get(), Math.max(diff1, diff2)));
        }

        if (right != null) {
            // 计算最值
            min = Math.min(right[0], min);
            max = Math.max(right[1], max);

            // 计算差值
            int diff1 = Math.abs(root.val - min);
            int diff2 = Math.abs(root.val - max);

            ai.set(Math.max(ai.get(), Math.max(diff1, diff2)));
        }

        return new int[]{min, max};
    }

    /**
     * 思路：
     * <p>
     * dfs，遍历所有路径，然后在路径中比较节点的差值，并记录最大值
     * <p>
     * 这个属于暴力求解，复杂度很高
     *
     * @param root
     * @return
     */
    public static int maxAncestorDiff(TreeNode root) {
        List<Integer> path = new ArrayList<>();

        AtomicInteger max = new AtomicInteger(Integer.MIN_VALUE);
        dfs(root, path, max);
        return max.get();
    }

    private static void dfs(TreeNode root, List<Integer> path, AtomicInteger max) {
        if (root == null) {
            return;
        }

        path.add(root.val);

        if (root.left == null && root.right == null) {
            for (int i = 0; i < path.size() - 1; i++) {
                for (int j = i + 1; j < path.size(); j++) {
                    int diff = Math.abs(path.get(i) - path.get(j));
                    max.set(Math.max(max.get(), diff));
                }
            }

            path.remove(path.size() - 1);
            return;
        }

        dfs(root.left, path, max);
        dfs(root.right, path, max);

        path.remove(path.size() - 1);
    }
}
